package basis.netease.medium;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 7-10 跳跃距离
 * 给定一个非负整数数组nums，最初位于数组的第一个位置；数组中的每个元素表示你在该位置可以跳跃的最大长度。
 * 请确定是否可以到达最后一个位置。
 * 输入格式:
 * 每个测试用例一行，以“,”分隔，代表nums数组
 * 输出格式:
 * 请确定是否可以到达最后一个位置。如果能，返回true，否则返回false
 * 输出样例1：
 * 在这里给出一组输入。例如：
 * 2,3,1,1,4
 * 输出样例1：
 * 在这里给出相应的输出。例如：
 * true
 * 输入样例2:
 * 在这里给出一组输入。例如：
 * 3,2,1,0,4
 * 输出样例2:
 * 在这里给出相应的输出。例如：
 * false
 */
public class Main_9 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums = Arrays.stream(scanner.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int lastIndex = nums.length - 1;
        System.out.println(dfs2(nums, lastIndex, 0));
    }

    public static boolean dfs2(int[] nums, int lastIndex, int x) {
        if (x == lastIndex) {
            // 到达最后一个位，成功返回
            return true;
        }
        if (x > lastIndex) {
            // 超出数组长度，失败返回
            return false;
        }
        if (nums[x] == -1) {
            // 已访问过，直接跳过
            return false;
        }
        int mx = nums[x];
        // 访问的位置置为-1
        nums[x] = -1;
        for (int i = 1; i <= mx; i++) {
            if (dfs2(nums, lastIndex, x + i)) {
                return true;
            }
        }
        return false;
    }

}
